/**
 * 
 */
package tree;


import java.util.Stack;
/**
 * @author michaelyi
 *
 */
public class BinarySearchTree<T> {

	TreeNode<T> root;
	/**
	 * 
	 */
	public BinarySearchTree() {
	}

	public boolean isBSTInterative(TreeNode<Integer> root) {
		if (null == root) return true;
		
		// pre order traversal and check the left and right children before push into stack
		Stack<TreeNode<Integer>> stack = new Stack<TreeNode<Integer>>();
		Stack<Integer> maxValues = new Stack<Integer>();
		Stack<Integer> minValues = new Stack<Integer>();
		stack.push(root);
		maxValues.push(Integer.MAX_VALUE);
		minValues.push(Integer.MIN_VALUE);

		while (!stack.isEmpty()) {
			TreeNode<Integer> node = stack.pop();
			int max = maxValues.pop();
			int min = minValues.pop();
			if (node.right != null) {
				if (node.right.data >= node.data && node.right.data <= max) {
					stack.push(node.right);
					maxValues.push(max);
					minValues.push(node.data + 1);
				}
				else
					return false;
			}
			
			if (node.left != null) {
				if (node.left.data <= node.data && node.left.data >= min) {
					stack.push(node.right);
					maxValues.push(node.data - 1);
					minValues.push(min);
				}
				else
					return false;
			}
		}
		
		return true;
	}
	
	public boolean isBSTInterative2(TreeNode<Integer> root) {
		if (null == root) return true;
		
		// pre order traversal and check the left and right children after pop from stack
		Stack<TreeNode<Integer>> stack = new Stack<TreeNode<Integer>>();
		Stack<Integer> maxValues = new Stack<Integer>();
		Stack<Integer> minValues = new Stack<Integer>();
		stack.push(root);
		maxValues.push(Integer.MAX_VALUE);
		minValues.push(Integer.MIN_VALUE);

		while (!stack.isEmpty()) {
			TreeNode<Integer> node = stack.pop();
			int max = maxValues.pop();
			int min = minValues.pop();
			if (node.data < min || node.data > max)
				return false;
			
			if (node.right != null) {
				stack.push(node.right);
				maxValues.push(max);
				minValues.push(node.data + 1);
			}
			
			if (node.left != null) {
				stack.push(node.right);
				maxValues.push(node.data - 1);
				minValues.push(min);
			}
		}
		
		return true;
	}
	
	
	public boolean isBSTInterative3(TreeNode<Integer> root) {
		boolean result = true;
		if (null == root) return result;
	
		// pre order traversal and check the left and right children after pop from stack
		Stack<TreeNode<Integer>> nodeStack = new Stack<TreeNode<Integer>>();
		Stack<Integer> maxStack = new Stack<Integer>();
		Stack<Integer> minStack = new Stack<Integer>();
		
		nodeStack.push(root);
		maxStack.push(Integer.MAX_VALUE);
		minStack.push(Integer.MIN_VALUE);
	
		
		while (!nodeStack.isEmpty()) {
			TreeNode<Integer> node = nodeStack.pop();
			int max = maxStack.pop();
			int min = minStack.pop();
			
			if (node.data <= max && node.data >= min) {
				if (node.right != null) {
					nodeStack.push(node.right);
					maxStack.push(max);
					minStack.push(node.data);
				}
				if (node.left != null) {
					nodeStack.push(node.left);
					maxStack.push(node.data);
					minStack.push(min);
				}
			}
			else {
				result = false;
				break;
			}
		}
		
		return result;
	}
	
	
	public boolean isBST(TreeNode<Integer> root) {
		
		
		return false;
	}
	
	public boolean isBSTRangeHelper(TreeNode<Integer> root, int high, int low) {
		if (null == root) {
			return true;
		}
		
		return (root.data.intValue() <= high && root.data.intValue() >= low)
			&& isBSTRangeHelper(root.left, root.data-1, low)
			&& isBSTRangeHelper(root.right, high, root.data+1);
	}
	
	
	
	


	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 

	}

}
